The teachings herein are directed to a method and apparatus for resizing a color halftone image using uniform rosette halftone tile parameters.
Demands imposed by today's digital media handling in regards to document edit-ability, portability, and dynamic layout make simple solutions for image resizing obsolete. Consider that a document can be rasterized and halftoned for a particular print path. That document may be directed to a different printer, possibly years later when extracted from an archive, with different paper size capabilities and may require image editing, cropping and resizing of halftoned image content prior to printing on the given print engine. Color halftone images may generally be re-purposed to print on different paper sizes and require layout modifications and resizing. Printed color halftone images may be scanned in a setting such as at a digital copier, and a user may wish to modify the image attributes such as size, aspect ratio, or image content. Conventional resizing methods that utilize spatially consistent interpolation methods are unsuitable in this halftone image setting because interpolation methods introduce defects in color halftone image structure and such spatially consistent interpolation can distort image content.
To begin, consider the halftone image class of concern to the present teachings herein. With the advent of inexpensive digital color printers, methods and systems of color digital halftoning have become increasingly important in the reproduction of printed or displayed images possessing continuous color tones. It is well understood that most digital color printers operate in a binary mode, i.e., for each color separation, a corresponding color spot is either printed or not printed at a specified location or pixel. Digital halftoning controls the printing of color spots, where the spatial averaging of the printed color spots by either a human visual system or a viewing instrument, provides the illusion of the required continuous color tones.
The most common halftone technique is screening, which compares the required continuous color tone level of each pixel for each color separation with one or more predetermined threshold levels. The predetermined threshold levels are typically defined for a rectangular cell that is tiled to fill the plane of an image, thereby forming a halftone screen of threshold values. At a given pixel, if the required color tone level is darker than the given halftone threshold level, a color spot is printed at that specified pixel. Otherwise the color spot is not printed. The output of the screening process is a binary pattern of multiple small “dots,” which are regularly spaced as is determined by the size, shape, and tiling of the halftone cell. In other words, the screening output, as a two-dimensionally repeated pattern, possesses two fundamental spatial frequencies, which are completely defined by the geometry of the halftone screen.
It is understood in the art that the distribution of printed pixels depends on the design of the halftone screen. For clustered-dot halftone screens, all printed pixels formed using a single halftone cell typically group into one or more clusters. If a halftone cell only generates a single cluster, it is referred to as a single-dot halftone or single-dot halftone screen. Alternatively, halftone screens may be dual-dot, tri-dot, quad-dot, or the like.
While halftoning is often described in terms of halftone dots, it should be appreciated that idealized halftone dots can possess a variety of shapes that include rectangles, squares, lines, circles, ellipses, “plus signs,” X-shapes, pinwheels, and pincushions, and actual printed dots can possess distortions and fragmentation of those idealized shapes introduced by digitization and the physical printing process. Various digital halftone screens having different shapes and angles are described in U.S. Pat. No. 4,149,194, the disclosure found therein is hereby incorporated by reference in its entirety.
A common problem that arises in digital color halftoning is the manifestation of moiré patterns. Moiré patterns are undesirable interference patterns that occur when two or more color halftone separations are printed over each other. Since color mixing during the printing process is a non-linear process, frequency components other than the fundamental frequencies and harmonics of the individual color halftone separations can occur in the final printout. For example, if an identical halftone screen is used for two color separations, theoretically, there should be no moiré patterns. However, any slight misalignment between the two color halftone separations occurring from an angular difference and/or a scalar difference will result in two slightly different fundamental frequency vectors. Due to nonlinear color mixing the difference in frequency vectors produces a beat frequency which will be visibly evident as a very pronounced moiré interference pattern in the output. To avoid, for example, two-color moiré patterns due to misalignment, or for other reasons, different halftone screens are commonly used for different color separations, where the fundamental frequency vectors of the different halftone screens are separated by relatively large angles. Therefore, the frequency difference between any two fundamental frequencies of the different screens will be large enough so that no visibly objectionable moiré patterns are produced.
In selecting different halftone screens, for example for three color separations, it is desirable to avoid any two-color moiré as well as any three-color moiré. It is well known that in the traditional printing industry that three halftone screens, which can be constructed by halftone cells that are square in shape and identical, can be placed at 15°, 45°, and 75°, respectively, from a point and axis of origin, to provide the classical three-color moiré-free solution.
However, for digital halftoning, the freedom to rotate a halftone screen is limited by the raster structure, which defines the position of each pixel. Since tan(15°) and tan(75°) are irrational numbers, rotating a halftone screen to 15° or 75° cannot be exactly implemented in digital halftoning. To this end, some methods have been proposed to provide approximate instead of exact moiré-free solutions. For example, in U.S. Pat. Nos. 5,323,245 and 5,583,660, this problem is approached by using a combination of two or more perpendicular, unequal frequency screen patterns and non-perpendicular, equal frequency non-conventional screen patterns. However, all these approximate solutions result in some halftone dots having centers that do not lie directly on addressable points, or on the pixel positions defined by the raster structure. Therefore, the shape and center location varies from one halftone dot to another. Consequently, additional interference or moiré between the screen frequencies and the raster frequency can occur. In another approach, U.S. Pat. No. 5,371,612 discloses a moiré prevention method to determine screen angles and sizes that is usable solely for square-shaped, halftone screens.
U.S. Pat. No. 6,798,539 to Wang et al., discloses methods for using single-cell, non-orthogonal clustered-dot screens to satisfy the moiré-free conditions for color halftoning. The disclosure also provides methods that combine single-cell non-orthogonal clustered-dot screens and line screens for moiré-free color halftoning. Particularly, the selection of these single-cell halftone screens is determined by satisfying moiré-free conditions provided in the respective spatial or frequency equations. The disclosure found in U.S. Pat. No. 6,798,539 is hereby incorporated by reference in its entirety.
In U.S. Patent Application Publication No. 2006/0170975 A1, Wang discloses a moiré-free color halftone configuration for clustered dots. Unlike conventional methods, the disclosed method produces periodic hexagon rosettes of identical shapes. These exemplary hexagon rosettes have three fundamental spatial frequencies exactly equal to half of the fundamental frequency of the three halftone screens. The resultant halftone outputs are truly moiré free, as all the fundamentals and harmonic frequencies are multiples of and thus higher in frequency than the rosette fundamental frequency. The disclosure found in US Publication No. 2006/0170975 A1 is hereby incorporated by reference in its entirety
In U.S. Patent Application Publication No. 2008/0130055 A1, Wang and Loce disclose a method and apparatus for moiré-free color halftone printing with up to four color image separations. The method and apparatus utilize a plurality of non-orthogonal halftone screens to produce outputs that are moiré free and form uniform periodic rosettes. The method and apparatus provide for defining a first and a second color halftone screen fundamental frequency vector for each of three halftone screens such that the halftone screen set output forms uniform hexagonal rosettes; then defining a fourth color halftone screen where a first fundamental vector of the fourth screen shares a fundamental frequency vector with one of said three halftone screens and a second fundamental frequency vector of the fourth screen shares a fundamental frequency vector with a different one of said three color halftone screens. The disclosure found in U.S. Patent Application Publication No. 2008/0130055 A1 is hereby incorporated by reference in its entirety.
In U.S. Patent Application Publication No. 2008/0130054, Wang and Loce disclose a method and apparatus for moiré-free enhanced color halftone printing of color image separations for an arbitrary number of colorants. The method and apparatus utilizes a plurality of halftone screens, >4, to produce outputs that are moiré free and form hexagonal periodic rosettes. The relatively large number of screens can be used for enhanced printing applications, such as printing with high-fidelity colorants, light colorants, or special colorants, such as white, metallics and fluorescents. The method and apparatus provide for defining rosette fundamental frequency vectors VR1, VR2 that satisfy a length and sum requirement to meet visual acceptability standards according to |VR1|>fmin, |VR2|>fmin, and |VR1±VR2|>fmin; defining N halftone screens for colorants i=1, N, respectively possessing first and second frequency vectors (Vi1, Vi2), where no two screens possess identical fundamental frequency vector pairs; and selecting fundamental frequency vectors for the N halftone screens according to (Vi1, Vi2)=(mi1VR1+mi2VR2, ni1VR1+ni2VR2) for integer m's and n's, where at least one fundamental frequency vector or its conjugate must also satisfy one of the following: Vik=VR1, Vik=VR2, and |Vik|>2 max [|VR1|, |VR2|]. The disclosure found in U.S. Patent Application Publication No. 2008/0130054 is hereby incorporated by reference in its entirety.
A current practice for resizing an image is to perform some type of resampling interpolation of the input image to generate an output image with the desired number of samples in each dimension. But, resampling a color halftone image with an interpolator such as nearest-neighbor, linear, quadratic, or cubic can result in defects within the color halftone image. One particularly problematic defect is the introduction of gray levels that must be re-halftoned prior to printing, where the re-halftoning step creates an interference pattern with the input color halftone image structure. Another defect is the appearance of seams along columns or rows of pixels, where the resampled halftone samples have a local disturbance in phase with respect to the halftone frequency. Yet another defect associated with these resampling methods is that the aspect ratio of important image content can become distorted. For example, use of resampling to reduce the vertical dimension of an image can make people appear shorter and wider than they are in reality.
Another practice for resizing a color halftone image is simply to crop that image to the desired size. However, cropping can delete desired image content around the borders of the color halftone image.
The diversity and versatility of display devices today imposes new demands on digital media. For instance, designers must create different alternatives for web-content and design different layouts for different display and rendering devices. These demands have lead to development of increasingly sophisticated image resizing tools for continuous tone digital images. Avidan and Shamir, in “Seam Carving for Content-Aware Image Resizing” ACM Transactions on Graphics, Volume 26, Number 3, SIGGRAPH 2007, present a simple image operator called seam carving, that supports content-aware image resizing for both image reduction and image expansion. A seam is an optimal eight-connected path of pixels on a single image from top to bottom, or left to right, where optimality is defined by a low value of an image energy function. By repeatedly carving out or inserting seams in one direction, Avidan and Shamir can change the aspect ratio of an image. By applying these operators in both directions they can retarget the image to a new size. The selection and order of seams protect the content of the image, as defined by the energy function. Seam carving can also be used for image content enhancement and object removal. The seam carving method of Avidan and Shamir can support various visual saliency measures for defining the energy of an image, and can also include user input to guide the process. By storing the order of seams in an image they create multi-size images that are able to continuously change in real time to fit a given size.
The method of Avidan and Shamir cannot be readily applied to color halftone images because selecting low energy seams will result in visually undesirable pathological seams that travel between halftone dots or along chains of connected dots. Removing a low-energy seam that travels between halftone dots would only increase the local darkness in the region about the seam. Conversely, removing a low-energy seam that traveled along connected halftone dots will decrease local darkness in the region about the seam. In either case, the seams would appear as visible streaks and would quite likely be objectionable. For example a simple single separation input halftone image where the pixels are at 600 dpi (dots per inch) resolution, and the halftone is at 141 cpi (cells per inch) at 45° when resized by 10% in the horizontal direction by applying a low energy seam removal method directly on the halftone image caused undesirable streaks to appear in the image.
One further option for resizing a halftone image is to apply a descreening technique to the halftone image to remove the halftone dot structure and provide a continuous tone version of the image. The continuous tone version of the image could be resized using the method of Avidan and Shamir. After resizing, the image may be re-halftoned to finally produce a resized binary image. However, a key problem with that approach is that any such descreening technique tends to blur fine details within an image and the resulting image will have an excessively “soft” appearance. This softness problem will be particularly evident when applied in binary printer image paths and copier image paths that utilize a “copy dot” approach to reproduction. “Copy dot” refers to direct copying of a halftone image without descreening and rescreening. Resizing such a descreened image will induce a blurring that “copy dot” reproduction is intended to avoid.
As provided herein, there are supplied teachings to systems and methods for resizing a digital uniform rosette halftone image composed of multiple colorant separations, by using uniform rosette halftone tile parameters and iterative determination of energy metrics. One approach entails receiving into a digital imaging system, a digital uniform rosette halftone image and a desired resizing factor for the digital uniform rosette halftone image. Subsequently the system will define uniform rosette screen parameters to define uniform rosette Holladay halftone tiles within the color uniform rosette digital halftone image. From the defined uniform rosette cells, a number of uniform rosette halftone tile seams are determined for deletion. The orientation of the number of uniform rosette halftone tile seams being dictated by the received desired resizing factor. The energy of the number of uniform rosette halftone tile seams is determined according to an energy metric so as to provide indication of low energy determined uniform rosette halftone tile seams. A resizing of the uniform rosette halftone image by iteratively deleting a number of the low energy determined uniform rosette halftone tile seam is performed so as to obtain a resized uniform rosette halftone image. The resized uniform rosette halftone image may then be printed on a printer.
Disclosed in embodiments herein is a method for reducing the size of a digital uniform rosette halftone image composed of multiple colorant separations where an iterative determination of energy metrics it utilized. The method provides receiving into a digital imaging system, a digital uniform rosette halftone image and a desired resizing factor for that digital uniform rosette halftone image. The system will then determine the uniform rosette halftone screen parameters for the digital uniform rosette halftone image. Uniform rosette cells within the digital uniform rosette halftone image from the determined uniform rosette halftone screen parameters are then defined. From the defined uniform rosette cells and determined uniform rosette halftone cell parameters, a number of uniform rosette halftone tile seams are determined for manipulation. The orientation of these uniform rosette halftone tile seams being dictated by the received desired resizing factor. The energy of the number of uniform rosette halftone tile seams is determined according to an energy metric so as to provide indication of a number of low energy determined uniform rosette halftone tile seams sufficient to achieve the desired resizing factor for the digital uniform rosette halftone image. A resizing of the uniform rosette halftone image by iteratively deleting the number of low energy determined uniform rosette halftone tile seams is performed to obtain a resized uniform rosette halftone image. The resized uniform rosette halftone image may then be printed on a printer.
Further disclosed in embodiments herein is an image forming method for reducing the size of a digital uniform rosette halftone image composed of multiple colorant separations where an iterative determination of energy metrics it utilized. The method entails receiving into a digital imaging system, a digital uniform rosette halftone image and a desired resizing factor for the digital uniform rosette halftone image. Uniform rosette cells within the digital uniform rosette halftone image are defined. From the defined uniform rosette cells, a number of uniform rosette halftone tile seams are determined for deletion. The orientation of these uniform rosette halftone tile seams being dictated by the received desired resizing factor. Each colorant separation of the digital uniform rosette halftone image is descreened to provide descreened pixel values. An energy metric from the descreened pixel values is determined so as to provide an energy map. The energy of the number of uniform rosette halftone tile seams is determined according to an energy map, so as to indicate of a number of low energy determined uniform rosette halftone tile seams in sufficient number to at least to achieve the desired resizing factor for the digital uniform rosette halftone image. A resizing of the uniform rosette halftone image is performed by iteratively deleting the number of low energy determined uniform rosette halftone tile seams, to obtain a uniform rosette resized halftone image. The resized uniform rosette halftone image may then be printed on a printer.